package Sort.BubbleSort;

import java.util.Arrays;

public class DaiBubble {

    /*
    代代编写的冒泡算法，等同于我所写Bubble2,其中三种交换方式属实大开眼界
     */

        //从第一数开始向后比较，前>后则交换位置，最大一个数会被移动到数组最后
        //从第一数开始向后比较，比较到数组倒数第二个数，前>后则交换位置，最大一个数会被移动到数组最后
        //不断循环，数组最小的数在最后也会冒到数组开始

        public int[] sort(int[] original) {
            int[] result = Arrays.copyOf(original, original.length);
            for (int i = 1; i < result.length; i++) {
                //标志是否一趟比较后，未做任何交换
                boolean flag = true;
                for (int j = 0; j < result.length - i; j++) {
                    if (result[j] > result[j + 1]) {
                        //临时变量交换
                        int temp = result[j];
                        result[j] = result[j + 1];
                        result[j + 1] = temp;
                        //加减法交换
                        result[j] += result[j + 1];
                        result[j + 1] = result[j] - result[j + 1];
                        result[j] -= result[j + 1];
                        //异或交换
                        result[j] ^= result[j + 1];
                        result[j + 1] ^= result[j];
                        result[j] ^= result[j + 1];

                        flag = false;
                    }
                }

                if (flag) {
                    break;
                }
            }
            return result;
        }

        public static void main(String[] args) {
            int[] original = {221412, 2134, 322, 2154, 1235, 3, 0, -1, -345};
            System.out.println("Original: " + Arrays.toString(original));
            int[] sorted = new DaiBubble().sort(original);
            System.out.println("Sorted: " + Arrays.toString(sorted));
        }
    }
